import java.util.List;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-05-11
 * Time: 16:47
 */
class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val){
        this.val = val;
    }
}
public class Solution3 {
    /*还有一种经典解法，核心思想是头插法，因为我们每次都需要翻转k个一组的小链表，所以我们可以先求出需要翻转多少组
    * 然后再分组去利用头插法翻转每一组链表，求出有多少组就需要遍历链表求出链表长度，然后去除以k就行了*/
    //头插法，四部曲，经典思想： 需要在该链表头结点借助一个外部的节点翻转
    /*          null---->1---->2---->3---->4
                 pre     head  tmp
                        cur
        头插法翻转：  1.先记录当前节点下一个节点 ；tmp=cur.next;
                     2.从当前节点的后一个节点开始一次让后面的节点换到前面来：
                                 需要先连接后面的：cur.next=tmp.next;
                                 翻转当前节点到后面：tmp.next=pre.next;
                                 连接上前面的：   pre.next=tmp;
    
    * */
    public ListNode reverseKGroup (ListNode head, int k) {
        if(head==null || head.next == null || k==1){
            return head;
        }
        //定义一个虚拟节点作为新的链表头
        ListNode newH = new ListNode(0);
        //反转的辅助节点，就是上一组翻转后的尾巴节点，这是头插法的关键点
        ListNode pre = newH;
        pre.next = head;
        //遍历到的当前节点
        ListNode cur = head;
        ListNode tmp = null; //当前节点的下一个节点
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        //开始分组翻转
        for (int i = 0; i < len / k; i++) {
            //k个节点只需要翻转k-1次
            for (int j = 1; j < k; j++) {
                tmp = cur.next;
                cur.next = tmp.next;
                tmp.next = pre.next;
                pre.next = tmp;
            }
            //翻转完一组，接着翻转下一组，需要借助一个前驱节点就是上一组翻转后的尾结点作为辅助
            pre = cur;
            cur = cur.next; //下一组的待反转头结点
        }
        //返回新的链表
        return newH.next;
    }
}
